package org.labuladong.动态规划算法.一维DP;

/**
 * @Auther: qingle
 * @Date: 2024/10/26-14:15
 * @Description:
 *
 * 给定⼀个整数数组 nums，找到⼀个具有最⼤和的连续⼦数组（⼦数组最少包含⼀个元素），返回其最⼤和。
 * 示例 1：
 * 输⼊：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续⼦数组 [4,-1,2,1] 的和最⼤，为 6。
 *
 * @version: 1.0
 */
public class LC_53大子序和 {

	public static int maxSubArray(int[] nums)
	{
		int max = nums[0];
		int sum = 0;

		for (int num : nums) {
			if (sum > 0) {
				sum += num;
			} else {
				sum = num;
			}
			max = Math.max(max, sum);
		}

		return max;
	}

	public static void main(String[] args)
	{
		int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
		int max = maxSubArray(nums);
		System.out.println(max);
	}
}
